#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    Node *next;
    Node *prev;
} Node;

Node *getNewNode(int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

void headInsert(Node **node, int data) {
    Node *newNode = getNewNode(data);
    if(*node == NULL) {
        *node = newNode;
        return;
    }
    newNode->next = *node;
    (*node)->prev = newNode;
    *node = newNode;
}

void tailInsert(Node **node, int data) {
    Node *newNode = getNewNode(data);
    if(*node == NULL) {
        *node = newNode;
        return;
    }
    Node *current = *node;
    while(current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
    newNode->prev = current;
}

void Insert(Node **node, int data, int pos) {
    if(pos < 1) {
        printf("ERROR: Invalid position.\n");
        return;
    }
    Node *current = *node;
    Node *newNode = getNewNode(data);
    if(pos == 1) {
        newNode->next = current;
        current->prev = newNode;
        *node = newNode;
        return;
    }
    for(int i = 0; i < pos - 1; i++) {
        if(current == NULL) {
            printf("ERROR:Out of range.\n");
            return;
        }
        current = current->next;
    }
    if(current == NULL) {
        free(newNode);
        tailInsert(node, data);
        return;
    }
    current->prev->next = newNode;
    newNode->prev = current->prev;
    newNode->next = current;
    current->prev = newNode;
}

void Remove(Node **node, int pos) {
    if(pos < 1) {
        printf("ERROR: Invalid position.\n");
        return;
    }
    Node *current = *node;
    if(pos == 1) {
        *node = current->next;
        current->next->prev = NULL;
        free(current);
        return;
    }
    for(int i = 0; i < pos - 1; i++) {
        if(current == NULL) {
            printf("ERROR:Out of range.\n");
            return;
        }
        current = current->next;
    }
    current->prev->next = current->next;
    if(current->next != NULL)
        current->next->prev = current->prev;
    free(current);
}

void Print(Node *node) {
    if(node == NULL) {
        printf("\n");
        return;
    }
    printf("%d ", node->data);
    Print(node->next);
}

void ReversePrint(Node *node) {
    if(node == NULL) {
        return;
    }
    ReversePrint(node->next);
    printf("%d ", node->data);
}

int main(void) {
    Node *head = NULL;
    headInsert(&head, 2);//2
    headInsert(&head, 8);//8 2
    headInsert(&head, 6);//6 8 2
    tailInsert(&head, 4);//6 8 2 4
    Remove(&head, 2);//6 2 4
    Insert(&head, 5, 3);//6 5 2 4
    Print(head);
    return 0;
}